
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 给定一个可包含重复数字的序列，返回所有不重复的全排列。与上一题不一样的是，需要增加重复的校验，方法是增加一个算法，判断是不是这个队列之前已经添加过
 * <p>
 * 示例:
 * <p>
 * 输入: [1,1,2]
 * 输出:
 * [
 * [1,1,2],
 * [1,2,1],
 * [2,1,1]
 * ]
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(permuteUnique(new int[]{1, 1, 2}).size());
    }


    /**
     * 使用mark记录使用情况
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        HashSet<String> set = new HashSet<>();
        int length = nums.length;
        boolean[] mark = new boolean[nums.length];
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                Integer[] child = new Integer[nums.length];
                child[0] = nums[i];
                if (1 == length) {
                    all.add(Arrays.asList(child));
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permuteUnique2(all, child, 1, nums, length, newMark, set);
                }
            }
        }
        return all;
    }

    /**
     * childLen表示当前记录的进度，使用集合去重，但是这样子成本还是太高了，不知道有没有算法层面可以控制的
     *
     * @param all
     * @param child
     * @param childLen
     * @param nums
     * @param length
     * @param mark
     */
    public static void permuteUnique2(List<List<Integer>> all, Integer[] child, int childLen, int[] nums, int length, boolean[] mark, HashSet<String> set) {
        for (int i = 0; i < length; i++) {
            if (!mark[i]) {
                Integer[] newChild = new Integer[nums.length];
                System.arraycopy(child, 0, newChild, 0, length);
                newChild[childLen] = nums[i];
                ++childLen;
                if (childLen == length) {
                    String key = Arrays.toString(newChild);
                    if (!set.contains(key)) {
                        all.add(Arrays.asList(newChild));
                        set.add(key);
                    }
                } else {
                    boolean[] newMark = new boolean[length];
                    // 如果当前mark没有人使用
                    System.arraycopy(mark, 0, newMark, 0, length);
                    newMark[i] = true;
                    permuteUnique2(all, newChild, childLen, nums, length, newMark, set);
                    // 回溯进度
                    --childLen;
                }
            }
        }
    }

    static boolean[] vis;

    /**
     * 回溯算法，vis记录使用记录，perm记录当前队列
     * @param nums
     * @return
     */
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public static void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                // 如果遇到已经使用，或者当前值等于上一个值且上一个值没有被使用
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }


}